package com.ssh;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import org.junit.Test;

public class LadderLength_127 {
	public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int n = wordList.size();
        boolean[] marked = new boolean[n];
		Queue<String> queue = new LinkedList<>();
		queue.add(beginWord);
		int len = 1;
		while(!queue.isEmpty()) {
			len++;
			int size = queue.size();
			while (size-- > 0) {
				String next = queue.poll();
				for (int i = 0; i < n; i++) {
					String getWord = wordList.get(i);
					if (marked[i] == true) {
						continue;
					}
					if (isTwoEquals(endWord,next)) {
						return len;
					}
					if (isTwoEquals(next,getWord)) {
						queue.add(getWord);
						marked[i] = true;
					}
				}
			}
		}
		return 0;
    }
	
	private boolean isTwoEquals(String beginWord, String endWord) {
		int len = beginWord.length();
		int n = 0;
		for (int i = 0; i < len; i++) {
			if (beginWord.charAt(i) == endWord.charAt(i)) {
				n++;
			}
		}
		if (n == len-1) {
			return true;
		}
		return false;
	}
	
	@Test
	public void test() {
		String[] a = {"hot","dot","dog","lot","log"};
		List<String> list = new ArrayList<>(Arrays.asList(a));
		System.out.println(ladderLength("hit","cog",list));
	}
}
